import random


# 方式一：使用异或和判断先手是否必胜
def nim_game(piles):
    xor_sum = 0
    for pile in piles:
        xor_sum ^= pile
    return xor_sum != 0


# 方式二：使用记忆化搜索的递归方法判断先手是否必胜
memo = {}
def nim_game2(piles):
    def is_winning_state(state):
        state_tuple = tuple(state)
        if state_tuple in memo:
            return memo[state_tuple]

        # 如果所有堆的物品数都为 0，当前状态是必败态
        if all(pile == 0 for pile in state):
            result = False
        else:
            result = False
            # 尝试所有可能的取法
            for i in range(len(state)):
                for j in range(1, state[i] + 1):
                    new_state = state.copy()
                    new_state[i] -= j
                    if not is_winning_state(new_state):
                        result = True
                        break

        memo[state_tuple] = result
        return result
    return is_winning_state(piles)

def nim_game3(piles):
    maxi = max(piles)
    sg = [0] * (maxi+1)
    # for i in range(1, maxi+1):
    #     appeared = [False] * (maxi+1)
    #     for j in range(0, i):
    #         appeared[j] = True
    #     for s in range(maxi + 1):
    #         if not appeared[s]:
    #             sg[i] = s
    #             break
    sg = [_ for _ in range(maxi+1)]
    print(piles)
    print(*[(f'sg({p})', sg[p]) for p in piles])
    xor = 0
    for pile in piles:
        xor ^= pile
    return xor != 0


# 对数器
def verifier(num_tests=100):
    for _ in range(num_tests):
        # 随机生成堆的数量
        num_piles = random.randint(1, 5)
        # 随机生成每堆物品的数量
        piles = [random.randint(1, 10) for _ in range(num_piles)]
        result1 = nim_game(piles)
        result2 = nim_game2(piles)
        result3 = nim_game3(piles)
        if not result1 == result2 == result3:
            print(f"验证失败！输入: {piles}, 方法 1 结果: {result1}, 方法 2 结果: {result2}")
            return False
    print("所有测试用例验证通过！")
    return True


if __name__ == "__main__":
    verifier()
